package pro.softzhang.algo.lc700;

import com.alibaba.fastjson.JSON;
import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.knowledge.KMonotonicStack;
import pro.softzhang.algo.flag.theme.TTemperature;
import pro.softzhang.algo.flag.x.XClassic;
import pro.softzhang.algo.flag.x.XOptimal;

import java.util.Stack;

/**
 * [1,1,1,0]
 */
@DRed
@TTemperature
public class LC739_DailyTemperatures {
    public static void main(String[] args) {
        int[] temperatures = {30,20,60};
        int[] result = new Solution1().dailyTemperatures(temperatures);
        System.out.println(JSON.toJSONString(result));
    }

    /**
     * https://leetcode.cn/problems/daily-temperatures/solution/dan-diao-zhan-jie-jue-xia-yi-ge-geng-gao-ldyw/
     */
    @KMonotonicStack
    @XOptimal
    @XClassic
    static
    class Solution {
        public int[] dailyTemperatures(int[] temperatures) {
            int[] days = new int[temperatures.length];
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < temperatures.length; i++) {
                while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) {
                    int idx = stack.pop();
                    days[idx] = i - idx;
                }
                stack.push(i);
            }
            return days;
        }
    }

    /**
     * 暴力，会超时。
     */
    static
    class Solution1 {
        public int[] dailyTemperatures(int[] temperatures) {
            int[] days = new int[temperatures.length];
            for(int i = 0; i < temperatures.length; i++) {
                for (int j = i + 1; j < temperatures.length; j++) {
                    if (temperatures[j] > temperatures[i]) {
                        days[i] = j - i;
                        break;
                    }
                }
            }
            return days;
        }
    }
}